package LK_DP;

public class DP_Day_4 {
    /**/
    /*给定一个非负整数数组 nums ，你最初位于数组的 第一个下标 。
    数组中的每个元素代表你在该位置可以跳跃的最大长度。
    判断你是否能够到达最后一个下标。
    解题思路:贪心思想,每个都跳一下,判断最大值能不能到答最后一个下标*/

    public boolean canJump(int[] nums) {
        int n = nums.length;
        int rightmost = 0;
        for (int i = 0; i < n; ++i) {
            if (i <= rightmost) {
                rightmost = Math.max(rightmost, i + nums[i]);
                if (rightmost >= n - 1) {
                    return true;
                }
            }
        }
        return false;
    }
    /*给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。
    每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说，
    如果你在 nums[i] 处，你可以跳转到任意 nums[i + j] 处:
    解题思路
    动态规划:需要一个dp数组来记录*/
    /*定义子问题:子问题是参数化的,原问题要能由子问题表示,一个子问题的解要能通过其他子问题的解求出
    写出子问题的递推关系:在写递推关系的时候，f(k)=max{f(k−1),H k−1+f(k−2)}要注意写上 k=0k=0k=0 和 k=1k=1k=1 的基本情况
    确定 DP 数组的计算顺序:在普通的动态规划题目中，99% 的情况我们都不需要用到备忘录方法，所以我们最好坚持用自底向上的 dp 数组*/

    public int jump(int[] nums) {
        int length = nums.length;
        int end = 0;
        int maxPosition = 0;
        int steps = 0;
        for (int i = 0; i < length - 1; i++) {
            maxPosition = Math.max(maxPosition, i + nums[i]);
            if (i == end) {
                end = maxPosition;
                steps++;
            }
        }
        return steps;
    }
}
